package com.haidechizi.leetcode;

public class _473_火柴拼正方形 {

    public boolean makesquare(int[] nums) {
        if (nums.length < 4) {
            return false;
        }
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }
        if (sum % 4 != 0) {
            return false;
        }

        int[] bucket = new int[4];
        return generate(0, nums, bucket, sum / 4);
    }

    private boolean generate(int i, int[] nums, int[] bucket, int target) {
        if (i >= nums.length) {
            return bucket[0] == target && bucket[1] == target && bucket[2] == target && bucket[3] == target;
        }
        for (int j = 0; j < 4; j++) {
            if (bucket[j] + nums[i] > target) {
                continue;
            }
            bucket[j] += nums[i];
            if (generate(i + 1, nums, bucket, target)) {
                return true;
            }
            bucket[j] -= nums[i];
        }
        return false;
    }

}
